package 中等.二分查找;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。
 * 一开始，nums 中所有下标都是未标记的，你的任务是标记 nums 中 所有 下标。
 * 从第 1 秒到第 m 秒（包括 第 m 秒），对于每一秒 s ，你可以执行以下操作 之一 ：
 * 选择范围 [1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。
 * 如果 nums[changeIndices[s]] 等于 0 ，标记 下标 changeIndices[s] 。
 * 什么也不做。
 * 请你返回范围 [1, m] 中的一个整数，表示最优操作下，标记 nums 中 所有 下标的 最早秒数 ，如果无法标记所有下标，返回 -1 。
 *
 * @ https://leetcode.cn/problems/earliest-second-to-mark-indices-i/description/
 * @date 2024/02/25
 */
public class 标记所有下标的最早秒数I {

    public static void main(String[] args) {

    }

    /**
     * 二分答案
     * 1，题意理解：
     * nums[i] 表示下标 i+1 需要复习 nums[i] 天才能考试
     * changeIndices[j] 表示下标 j 如果已经复习了 num[j-1] 天的话，可以考试
     * 2，二分的前提：
     * 时间秒数越大，越容易完成所有考试，是单调的
     * 3，怎么判断 s 秒是否可以完成所有考试：
     * 对于相同的下标考试，越晚考试越有利，如果当前天是某个下标的最晚考试时间，就
     * 必须考试，并且需要判断是否之前是否有时间复习这个下标的所有天数
     */
    public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
        int left = 1, right = changeIndices.length;
        int ans = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (isAllMark(nums, changeIndices, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    private boolean isAllMark(int[] nums, int[] changeIndices, int time) {
        // 连考试的时间都不足
        if (time < nums.length) {
            return false;
        }
        Map<Integer, Integer> lastIdxMap = new HashMap<>();
        for (int i = 0; i < time; i++) {
            lastIdxMap.put(changeIndices[i], i);
        }
        // 考试的下标不是全部的课程
        if (lastIdxMap.size() != nums.length) {
            return false;
        }

        int cnt = 0;
        for (int i = 0; i < time; i++) {
            if (i == lastIdxMap.get(changeIndices[i])) {
                // 必须考试
                if (cnt < nums[changeIndices[i] - 1]) {
                    return false;
                }
                cnt -= nums[changeIndices[i] - 1];
            } else {
                cnt++;
            }
        }
        return true;
    }

}
